/*

http://codekata.pragprog.com/2007/01/kata_two_karate.html

Alberto Massa
11th of April, 2010

-- controllata la soluzione sul sedgewick.
2 ore.
2 errori:
nel calcolare i nuovi indici
nel calcolare il mediano
*/

#include <stdio.h>
#include <math.h>

#include "1test.c"

void main(void) {
	printf("Dicotomic search - karate chop\n");
	printf("first version, iterative array.\n");

	test();

	printf("\n.\n");
}

int logbasetwo(int x) {
	return (int)(log(x)/log(2))+1;
}

int chop(int n, int *in, int inlength) {

	int 
	i = 0,	// for loop
	arraylength = inlength, //sizeof(in)/sizeof(int),
	index = -1, // index of result
	///* not used */deep = logbasetwo(arraylength), // dicotomic search is O(lg(n)) algorithm
	l = 0, // left index
	r = arraylength-1,	// right index
	x;

	if(arraylength==0) return -1;

	//--------------------------------------------------- Dicotomic search
	///* not used */for(i=0; i<deep+1; i++) { // note: use option -std=c99 or -std=gnu99 to compile your code
	while(l<r+1){
		index = (r+l)/2;
		x = in[index];
		if (x == n) break;
		else {
			if(n>x) l = index+1;
			else r = index-1;						
		}
		index = -1;		
	}
	printf("chop > retrun %d\n", index);
	return index;
}
